import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-16-分割等和子集
 * @date 2025/8/17 15:10
 */
public class Solution416 {
    /*public static boolean canPartition(int[] nums) {
        int n = nums.length;
        // 长度小于2，无法分割
        if (n < 2) return false;
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        int target = sum / 2;
        // 总和为奇数或者最大值大于总和的一半，无法分割
        if (sum % 2 != 0 || maxNum > target) return false;

        // 若存在子集和为target，则return true
        // dp[i][j]代表能不能利用从下标0-i的nums元素值累加为j
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;

        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n-1][target];
    }*/

    /**
     * 简化空间复杂度
     *
     * @param nums
     * @return
     */
    public static boolean canPartition(int[] nums) {
        int n = nums.length;
        // 长度小于2，无法分割
        if (n < 2) return false;
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        int target = sum / 2;
        // 总和为奇数或者最大值大于总和的一半，无法分割
        if (sum % 2 != 0 || maxNum > target) return false;

        // 若存在子集和为target，则return true
        // dp[i]代表能不能利用从下标0-n-1的nums元素值累加为i
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; j--) {
                dp[j] |= dp[j - num];
            }
        }

        return dp[target];
    }

    public static void main(String[] args) {
        canPartition(new int[]{2, 2, 1, 1});
    }
}
